This invention relates generally to file systems, and more particularly to systems and methods that allocate data storage to facilitate access and retrieval of data in storage devices.
State of the art random-access data storage devices include magnetic disks drives, optical drives, solid-state drives and random access memories. They are typically managed by interfaces that reflect the capabilities and limitations of the underlying physical devices. The historic organizational model for random-access storage interfaces is that of a logical or physical disk unit having a given number of platters, cylinders, tracks and sectors. Modern storage devices have standardized around the concepts of blocks and block addresses
Applications, operating systems and databases generally delegate most of the work involved in managing random-access devices to file systems which are responsible for organizing data blocks and block addresses into more manageable organizational units such as files and directories. Two important organizational subsystems within a file system are the storage subsystem and the metadata subsystem. The storage subsystem manages which blocks belong to which files, tracks the order of blocks within each file, and tracks the blocks which are unused and are free for future allocation to a file in order to support operating system interfaces, such read, write, seek, etc. The metadata subsystem, on the other hand, manages the names and attributes of files, and tracks file access activity to support the higher-level operating system interfaces such as open, close, rename, etc. The performance of a file system is characterized by how efficiently it supports a given pattern of file access. File system performance, which is a significant factor in the performance of operating systems, applications and databases, is often a bottleneck because an application cannot begin to work on data until the file system guides the operating system in locating and transferring the data. File systems should facilitate the location and transfer of data as efficiently as possible given a particular configuration of random-access devices which may have different storage and I/O characteristic. In large storage systems particularly, significant time is frequently required merely to locate desired data and to allocate space for storing data so that it may be retrieved efficiently.
Another contributor to the overall efficiency of a file system is its ability to support periodic or dynamic reorganization of the file data to prevent or eliminate fragmentation, increase locality of commonly accessed data, and to migrate infrequently accessed data to appropriate storage areas or devices. This requires efficient access to the details of file system data allocation. Locating data in large storage systems, for example, is particularly time-consuming and burdensome. Utilities intended to improve file organization, such as commonly used defragmentation tools, are typically quite inefficient and significantly increase the I/O and processing burden of CPUs. What is needed is a mechanism that affords efficient access to a file system's underlying allocation of data with minimal overhead.
It is desirable to provide systems and methods for allocating data that address the foregoing and other problems with known file system data allocation approaches and that afford efficient access and retrieval of data in data storage devices. It is to these ends that the present invention is directed.